翻訳と辞書 Words near each other ・ Eulima kawamurai ・ Eulima koeneni ・ Eulima labiosa ・ Eulima lacca ・ Eulima lactea ・ Eulima langleyi ・ Eulima lapazana ・ Eulima latipes ・ Eulima leachi ・ Eulima legrandi ・ Eulima leptostoma ・ Eulima leptozona ・ Eulima lodderae ・ Euler's Disk ・ Euler's equations (rigid body dynamics) ・ Euler's factorization method ・ Euler's flycatcher ・ Euler's formula ・ Euler's four-square identity ・ Euler's identity ・ Euler's laws of motion ・ Euler's pump and turbine equation ・ Euler's rotation theorem ・ Euler's sum of powers conjecture ・ Euler's theorem ・ Euler's theorem (differential geometry) ・ Euler's theorem in geometry ・ Euler's three-body problem ・ Euler's totient function ・ Eulerian matroid Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Euler's factorization method ： ウィキペディア英語版 Euler's factorization method Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways. For example the number $1000009$ can be written as $1000^2\; +\; 3^2$ or as $972^2\; +\; 235^2$ and Euler's method gives the factorization $1000009\; =\; 293\; \backslash cdot\; 3413$. The idea that two distinct representations of an odd positive integer may lead to a factorization was apparently first proposed by Marin Mersenne. However, it was not put to use extensively until Euler one hundred years later. His most celebrated use of the method that now bears his name was to factor the number $1000009$, which apparently was previously thought to be prime even though it is not a pseudoprime by any major primality test. Euler's factorization method is more effective than Fermat's for integers whose factors are not close together and potentially much more efficient than trial division if one can find representations of numbers as sums of two squares reasonably easily. Euler's development ultimately permitted much more efficient factoring of numbers and, by the 1910s, the development of large factor tables going up to about ten million. The methods used to find representations of numbers as sums of two squares are essentially the same as with finding differences of squares in Fermat's factorization method. The great disadvantage of Euler's factorization method is that it cannot be applied to factoring an integer with any prime factor of the form 4''k'' + 3 occurring to an odd power in its prime factorization, as such a number can never be the sum of two squares. Even odd composite numbers of the form 4''k'' + 1 are often the product of two primes of the form 4''k'' + 3 (e.g. 3053 = 43 × 71) and again cannot be factored by Euler's method. This restricted applicability has made Euler's factorization method disfavoured for computer factoring algorithms, since any user attempting to factor a random integer is unlikely to know whether Euler's method can actually be applied to the integer in question. It is only relatively recently that there have been attempts to develop Euler's method into computer algorithms for use on specialised numbers where it is known Euler's method can be applied. ==Theoretical basis== The Brahmagupta–Fibonacci identity states that the product of two sums of two squares is a sum of two squares. Euler's method relies on this theorem but it can be viewed as the converse, given $n\; =\; a^2\; +\; b^2\; =\; c^2\; +\; d^2$ we find $n$ as a product of sums of two squares. First deduce that :$a^2\; -\; c^2\; =\; d^2\; -\; b^2$ and factor both sides to get :$(a-c)(a+c)\; =\; (d-b)(d+b)$ (1) Now let $k\; =\; \backslash operatorname(a-c,d-b)$ and $h\; =\; \backslash operatorname(a+c,d+b)$ so that there exists some constants $l,m,l\text{'},m\text{'}$ satisfying * $(a-c)\; =\; kl$, * $(d-b)\; =\; km$, $\backslash operatorname(l,m)\; =\; 1$ * $(a+c)\; =\; hm\text{'}$, * $(d+b)\; =\; hl\text{'}$, $\backslash operatorname(l\text{'},m\text{'})\; =\; 1$ Substituting these into equation (1) gives :$klhm\text{'}\; =\; kmhl\text{'}$ Canceling common factors yields :$lm\text{'}\; =\; l\text{'}m$ Now using the fact that $(l,m)$ and $(l\text{'},m\text{'})$ are pairs of relatively prime numbers, we find that * $l\; =\; l\text{'}$ * $m\; =\; m\text{'}$ So * $(a-c)\; =\; kl$ * $(d-b)\; =\; km$ * $(a+c)\; =\; hm$ * $(d+b)\; =\; hl$ We now see that $m\; =\; \backslash operatorname(a+c,d-b)$ and $l\; =\; \backslash operatorname(a-c,d+b)$ Applying the Brahmagupta–Fibonacci identity we get :$(k^2\; +\; h^2)(l^2\; +\; m^2)\; =\; (kl\; -\; hm)^2\; +\; (km\; +\; hl)^2\; =\; ((a-c)\; -\; (a+c))^2\; +\; ((d-b)\; +\; (d+b))^2\; =\; (2c)^2\; +\; (2d)^2\; =\; 4n,$ :$(k^2\; +\; h^2)(l^2\; +\; m^2)\; =\; (kl\; +\; hm)^2\; +\; (km\; -\; hl)^2\; =\; ((a-c)\; +\; (a+c))^2\; +\; ((d-b)\; -\; (d+b))^2\; =\; (2a)^2\; +\; (2b)^2\; =\; 4n.$ As each factor is a sum of two squares, one of these must contain both even numbers: either $(k,\; h)$ or $(l\; ,m)$. Without loss of generality, assume that pair $(k,h)$ is even. The factorization then becomes :$n\; =\; ((\backslash tfrac)^2\; +\; (\backslash tfrac)^2)(l^2\; +\; m^2).\; \backslash ,$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Euler's factorization method」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.